package com.wtgroup.demo.leetcode.q046_全排列;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/26 10:27
 */
public class Q046_My1 {

    /**
     * 暴力递归
     *
     * 逻辑: 6分;
     * LC 的回溯法不好理解.
     */
    public List<List<Integer>> permute(int[] nums) {
        return this.permute0(nums, 0, nums.length - 1);
    }

    private List<List<Integer>> permute0(int[] nums, int left, int right) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = right - left + 1;
        if (len==0) {
            return ans;
        }
        if (len==1) {
            ArrayList<Integer> one = new ArrayList<>();
            one.add(nums[left]);
            ans.add(one);
            return ans;
        }

        int first = nums[left];
        List<List<Integer>> lists = permute0(nums, left+1, right);
        for (List<Integer> restComp : lists) {
            for (int i = 0; i <= restComp.size(); i++) { // 多一个位置可插入
                List<Integer> allComp = new ArrayList<>(restComp);
                // i 位置插入 first
                allComp.add(i, first);
                ans.add(allComp);
            }
        }

        return ans;
    }

}
